#include "mat_pathfinding.h"
#include "mat_logicboard.h"
#include "mat_gamerule.h"

#include "num/rand.h"
		
#include <algorithm>
#include <cmath>        // std::abs
		
MATPathFinding::MATPathFinding() :	m_IsFound(false),
									m_LastStartX(-1),
									m_LastStartY(-1),
									m_LastEndX(-1),
									m_LastEndY(-1),
									m_IsDirty(false)
{
	for(int y = 0; y< MATGameRule::Instance().GetBoardCountY(); y++)
	{
		for(int x = 0; x < MATGameRule::Instance().GetBoardCountX(); x++)
		{
			m_TileA[y][x].m_X = x;
			m_TileA[y][x].m_Y = y;
			m_TileA[y][x].m_G = 0;
			m_TileA[y][x].m_H = x;
			m_TileA[y][x].m_pParent = NULL;
		}
	}

}
		
void	MATPathFinding::Reset()
{
	m_IsFound = false;
	m_IsDirty = false;
	m_LastStartX = m_LastStartY = m_LastEndX = m_LastEndY = -1;
	//m_PathA.resize(0);

}
		
void	MATPathFinding::DoPathFinding( int StartY, int StartX, int EndY, int EndX) 
{
	
	m_IsDirty = false;	

	if(	StartX == m_LastStartX && 
		StartY == m_LastStartY && 
		EndX == m_LastEndX &&
		EndY == m_LastEndY)		
		return;

	m_IsFound = false;
	m_LastStartX = StartX;
	m_LastStartY = StartY;
	m_LastEndX = EndX;
	m_LastEndY = EndY;

	if (StartY ==  EndY && StartX == EndX)
		return;		
	
	m_PathA.resize(0);
	
	m_OpenList.resize(0);
	m_CloseList.resize(0);
		
	Tile* TileStart = &m_TileA[StartY][StartX];
	TileStart->m_G = 0;
	TileStart->m_H = 0;
	TileStart->m_pParent = NULL;

	Tile* TileCurrent = TileStart;
	Tile* TileEnd = &m_TileA[EndY][EndX];
	MATGem* pGem;
	
	m_OpenList.push_back(TileCurrent);
	int SearchIndex;
	
	while (m_OpenList.size() > 0 ) 
	{
		TileCurrent = FindSmallestCostTile();
		
		
		SearchIndexInList(m_OpenList,TileCurrent,SearchIndex);
		m_OpenList.erase(m_OpenList.begin() + SearchIndex);				   
		m_CloseList.push_back(TileCurrent);
		
		
		if ( TileCurrent != TileEnd) 
		{				
				
			for (int i = 0; i < 4; i++)
			{
				int x; 
				int y; 

				if (i == 0 )
				{
					x = -1;
					y = 0;
				}
				else if (i == 1)
				{
					x = 1;
					y = 0;
				}
				else if (i == 2)
				{
					x = 0;
					y = 1;
				}
				else if (i == 3)
				{
					x = 0;
					y = -1;
				}

				if (!IsXYWithinGrid(TileCurrent->m_Y + y , TileCurrent->m_X + x))
					continue;
				
				
				Tile* TileNeighbour = &m_TileA[TileCurrent->m_Y + y][TileCurrent->m_X + x]; 
				
				pGem = MATLogicBoard::Instance().GetContentAt(TileNeighbour->m_Y, TileNeighbour->m_X);
				if( (!pGem ||
					(pGem && pGem->m_IsSmall))  &&
					MATLogicBoard::Instance().GetTileAt(TileNeighbour->m_Y, TileNeighbour->m_X) < TILE_UNREACHABLE					
					)
				{
					if( SearchIndexInList(m_CloseList, TileNeighbour, SearchIndex) == true)
						continue;
								
					if(SearchIndexInList(m_OpenList, TileNeighbour, SearchIndex) == true)				
					{  
						if (TileNeighbour->m_G > TileCurrent->m_G + 1)
						{
							TileNeighbour->m_pParent = TileCurrent;
							TileNeighbour->m_G = TileCurrent->m_G + 1;
						}
						
					}
					else
					{  							
						m_OpenList.push_back(TileNeighbour);
						TileNeighbour->m_pParent = TileCurrent;
						TileNeighbour->m_G = TileCurrent->m_G + 1;
						
						TileNeighbour->m_H = TileNeighbour->m_X - TileEnd->m_X 
											+  TileNeighbour->m_Y - TileEnd->m_Y;
						
					}
					
				}
			}
				
		}
		else 
		{ 
			m_IsDirty = true;
			m_IsFound = true;			
			Tile* TilePath = TileEnd;

			m_PathA.resize(0);
			do 
			{
				//push the position  of each tile into the arry, this position is relative to map.
				m_PathA.push_back(TilePath);
				TilePath = TilePath->m_pParent;
				
			}while (TilePath != TileStart);
				
			m_PathA.push_back(TilePath);
			std::reverse(m_PathA.begin(),m_PathA.end());		
			
			break;
		}
	
	} //end of while
	
	
	
	
	
}
		
		
		
		
MATPathFinding::Tile*	MATPathFinding::FindSmallestCostTile()
{
	int min = 10000;
	Tile* resTile = NULL;

	if (m_OpenList.size() == 0)
		return NULL;
	
	for (int j = 0; j < (int)m_OpenList.size(); j++)
	{
		Tile* tmpTile = m_OpenList[j];
		if (tmpTile->m_G + tmpTile->m_H < min)
		{
			min = tmpTile->m_G + tmpTile->m_H;
			resTile = tmpTile;
			
		}
		else if (tmpTile->m_G + tmpTile->m_H == min)
		{
			min = tmpTile->m_G + tmpTile->m_H;
			if (num::RAND32::Instance().RandInt(0,1) == 1)
				resTile = tmpTile;
			
		}
		
	}
	return resTile;
	
}

bool		MATPathFinding::IsXYWithinGrid(int Y, int X)
{
	if( Y >= MATGameRule::Instance().GetBoardCountY())
		return false;

	if( X >= MATGameRule::Instance().GetBoardCountX())
		return false;

	if( X < 0)
		return false;

	if( Y < 0) 
		return false;

	return true;
}

bool		MATPathFinding::SearchIndexInList(std::vector<Tile*>& VList, Tile* TileSearch, int& SearchIndex)
{
	std::vector<Tile*>::iterator Iter = std::find(VList.begin(), VList.end(), TileSearch);
	SearchIndex = std::distance(VList.begin(), Iter);

	if(SearchIndex >= (int)VList.size())
		return false;

	return true;
}
		

		
	
